/*
 * com.future CO.,ltd.
 */

package com.future;

import java.util.HashMap;
import java.util.Map;

/**
 * Description: ��ˢ���12
 * ����һ��δ������������� nums ���ҳ���������������У���Ҫ������Ԫ����ԭ�������������ĳ��ȡ�
 * <p>
 * ������Ʋ�ʵ��ʱ�临�Ӷ�Ϊ?O(n) ���㷨��������⡣
 * <p>
 * ʾ�� 1��
 * <p>
 * ���룺nums = [100,4,200,1,3,2]
 * �����4
 * ���ͣ���������������� [1, 2, 3, 4]�����ĳ���Ϊ 4��
 * ʾ�� 2��
 * <p>
 * ���룺nums = [0,3,7,2,5,8,4,6,0,1]
 * �����9
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode-cn.com/problems/longest-consecutive-sequence
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @Author: future
 * @Date:2022/4/9:15:02
 */
public class Solution_128 {

    public static void main(String[] args) {
        int[] nums = {100, 4, 200, 1, 3, 2};
        System.out.println(longestConsecutive(nums));
    }

    /**
     * ˼·��
     * 1����ÿһ����num����key��map��valueΪ�Ը�key��ͷ���߽�β�������ĸ�����Ĭ��Ϊ1
     * 2��Ȼ����num-1,��num-1��β��������������preLen
     * 3�����num+1,��num+1��β��������������postLen
     * 4����ô��ǰnum�ĳ���ΪpreLen+postLen+1
     * <p>
     * nums = {100, 4, 200, 1, 3, 2};
     * 1��key=100,val=1
     * ǰһ��key=99������,preLen=0
     * ��һ��key=101������,postLen=0
     * 2��key=4,val=1
     * ǰһ��key=3������,preLen=0
     * ��һ��key=4������,postLen=0
     * 3��key=200,val=1
     * ǰһ��key=199������,preLen=0
     * ��һ��key=201������,postLen=0
     * 4��key=1,val=1
     * ǰһ��key=0������,preLen=0
     * ��һ��key=2������,postLen=0
     * 5��key=3,val=1
     * ǰһ��key=2������,preLen=0
     * ��һ��key=4���ڣ�postLen=1
     * 6��key=2,val=1
     * ǰһ��key=1����,preLen=1+1
     * ��һ��key=3���ڣ�����postLen=2+1
     *
     * @param nums
     * @return
     */
    public static int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int ans = 1;
        Map<Integer, Integer> map = new HashMap<>();
        for (Integer num : nums) {
            if (!map.containsKey(num)) {
                // ǰһ����
                int preLen = map.get(num - 1) == null ? 0 : map.get(num - 1);
                // ǰһ����
                int postLen = map.get(num + 1) == null ? 0 : map.get(num + 1);
                // �ܳ���
                int allLen = preLen + postLen + 1;
                map.put(num, allLen);
                map.put(num - preLen, allLen);
                map.put(num + postLen, allLen);
                ans = Math.max(ans, allLen);
            }
        }
        return ans;
    }

}
